In communication systems in which multiple sources of information share the same communications channel, a method for regulating access to the common channel that is fair (however fairness is defined) to all the sources of information is always needed. The method of regulating sequential access to the common medium amongst all the sources of information is known as the arbitration method.
One typical communication system is made of multiple communication modules, each equipped with a transmitter and a receiver, interconnected by a common bus to which all the modules have access for transmission and reception. Communication between the modules takes place when one of the modules accesses the bus for a predetermined period of time and uses that time to transmit a finite amount of information to one of more receiving modules. Typically only one transmitter can have access to the shared medium at any given time. When more than one module wishes to transmit into the medium at the same time, which is a typical occurrence in packet mode communications, a conflict arises. The bus arbitration mechanism resolves the conflict created by the simultaneous requests to use the shared bus.
Based on the physical location of the arbitration, packet oriented communications buses have used one of two arbitration methods: centralized, or distributed. In a centralized arbitration method, a specialized piece of equipment, called an arbiter, sits in a central part of the bus collecting requests from all the communicating modules and resolving contentions created by simultaneous access requests from multiple modules. In a distributed arbitration method on the other hand, there is no arbiter per se; instead the communicating modules resolve their contention problems in a democratic manner by exchanging some form of arbitration information amongst themselves. One example of a distributed arbitration method is a token passing algorithm, implemented either in a bus or in a ring.
Distributed arbitration algorithms have been and continue being successfully implemented in many commercial packet communications systems, but they exhibit a number of deficiencies. One deficiency is that their performance tends to degrade with speed and distance. This is due to the finite amount of time that it takes for the distributed contention to be resolved, for instance, the amount of time that it takes for the token to change hands, or the time that it takes for certain signal levels to settle. This latency results in a less than 100% maximum utilization of the shared bus bandwidth. In other words, bandwidth is wasted while the modules decide who should access the bus next. Another deficiency of the distributed arbitration method is that in many instances the fairness of the arbitration method degrades as the distance between communication modules or the speed of the shared bus increases. A centralized arbitration method on the other hand may be conceived that is perfectly fair regardless of speed of distance.
Arbitration mechanisms in the past were devised for packet communications, which for the most part are not time-sensitive forms of communication. In these older arbitration methods, contentions between simultaneous requests for bus access are resolved in a first-come/first-serve basis, or in a round-robin fashion, or in any other fashion that is considered fair and equitable to all the communicating modules. Even when the arbitration method supports multiple priorities, these priorities are normally not associated with a time-constrained class of requests. In other words, requests are not tied to the time they were issued, and therefore there is no concept of the increasing urgency of a given request as time elapses without the request being granted. For these reasons, the majority of the packet communication arbitration methods developed in the past are not suitable to the support of real-time-demanding forms of communication such as voice or video communications. This is a widely known fact; successful commercial products such as CSMA/CD buses or token passing rings perform poorly if used to carry voice or video traffic.
A widely used solution to enhance the real-time traffic carrying capabilities of a communication bus is to divide its available capacity into a number of fixed size bandwidth slices, each slice occupying a fixed amount of time to transmit into the bus. The time slices are better known as time slots. This type of bus is usually referred to as a slotted bus. Each of the time slots can be used to transmit and receive a fixed amount of information (normally a small amount, such as 64 octets). This bus structure has the advantage or reducing the access latency to the bus, since in the case of multiple simultaneous requests to access the bus no single transmitter could monopolize the bus for longer than one time slot.
In a non-slotted bus on the other hand, a single transmitter could obtain access to the bus and begin transmission of a long file, for instance, without the ability to preempt the transfer if other more real-time demanding forms of communication were in need of accessing the bus. But even if a slotted bus is better suited than a non-slotted bus to support both real-time and non-real-time forms of communication concurrently, the arbitration method employed in conjunction with the slotted bus, as explained before, could still be non-optimal for the support of both real-time and non-real-real time communications.
Consequently, a new arbitration mechanism for a slotted bus must be developed that is capable of efficiently support new forms of communication, both real-time demanding and real-time tolerant. The new arbitration mechanism must take into consideration multiple priority levels defined by their access delay requirements, and must grant access to the shared bus in a fair manner according to the delay priority of the requests. This invention describes a centralized arbitration method for a slotted bus. The arbitration method supports multiple priority levels of both real-time and non-real time communication forms.